package Sort;

import java.util.Arrays;
import java.util.Date;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2022-04-18 11:38
 */
public class Down2UpMergeSort<T extends Comparable<T>> extends Sort<T>  {
    protected T[] temp;
    protected void merge(T[] nums,int l,int mid,int r){
        int i=l,j=mid+1;
        for (int k = l; k<=r ; k++) {
            temp[k]=nums[k];
        }
        for (int k = l; k <=r ; k++) {
            if (i>mid){
                //前半部分已经合并完成
                nums[k]=temp[j++];
            }else if (j>r){
                nums[k]=temp[i++];
            }else if (temp[i].compareTo(temp[j])<=0){
                nums[k]=temp[i++];//先将前半部小的时候合并，保证稳定性
            }else {
                nums[k]=temp[j++];
            }
        }
    }
    @Override
    public void sort(T[] nums) {
        int n=nums.length;
        temp= (T[]) new Comparable[nums.length];
        for (int sz = 1; sz < n; sz+=sz) {
            for (int l = 0; l < n-sz; l+=sz+sz) {
                merge(nums,l,l+sz-1, Math.min(l+sz+sz-1,n-1));
            }
        }
    }
    public static void main(String[] args) {
        Integer[] nums={3,5,6,4,1,2};
        Down2UpMergeSort<Integer> down2UpMergeSort=new Down2UpMergeSort<Integer>();
        down2UpMergeSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
